BOJ_14888_연산자 끼워넣기

깊이 우선 탐색(DFS)으로 주어진 수열 중간에 연산자를 끼워 넣어서 최대 최소를 구하는 문제

연산자를 순열로 줄 세워서 넣어주면 된다

연산자 배열을 4개로 만들지 않고 N-1 개로 줬는데 4개로 주고 나중에 dfs에서 해당 배열값이 0인지 아닌지 확인해도 된다. visited 배열도 안 써도 된다

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJO_14888_연산자끼워넣기 {
    /*
    연산자를 줄 세우는 문제
     */
    static int[] math;
    static int[] nums;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        nums = new int[N];
        math = new int[N - 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for (int i = 0; i < 4; i++) {
            int cnt = Integer.parseInt(st.nextToken());
            for (int j = 0; j < cnt; j++) {
                math[idx++] = i;
            }
        }

        dfs(new boolean[math.length], nums[0], 0);
        System.out.println(max);
        System.out.println(min);
    }

    static void dfs(boolean[] visited, int num, int count) {
        if (count == math.length) {
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }

        for (int i = 0; i < math.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int temp = num;
                switch (math[i]) {
                    case 0 -> temp += nums[count + 1];
                    case 1 -> temp -= nums[count + 1];
                    case 2 -> temp *= nums[count + 1];
                    case 3 -> temp /= nums[count + 1];
                }

                dfs(visited, temp, count + 1);
                visited[i] = false;
            }
        }
    }
}